package 面试经典150题.二分查找;

/**
 * @author tmh
 * @date 2024/6/8 20:43
 * @description 找8的最大值的下标，归根结底就是找9的下标加上-1即可，因为返回的值是left，如果数组里面没得left的这个值，那么left返回的就是比target大一点的最小数字(数组中)
 * 参考链接：https://www.bilibili.com/video/BV1AP41137w7/?vd_source=999036f6f8c94ed7a56d33b4c100249d
 */
public class T34在排序数组中查找元素的第一个和最后一个位置 {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        int target = 8;
        for (int i : searchRange(nums, target)) {
            System.out.println(i);
        }

    }

    public static int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        //这个代表的是目标值为9的左边那个数
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};

    }

    // 闭区间写法
    private static int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            } else {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            }
        }
        return left;
    }

}
